A way of constructing error-correcting codes that are both powerful and can be efficiently decoded is to combine two or more smaller codes, called constituent codes, to form a larger composite code, with the decoding of the larger composite code being accomplished in an iterative manner using soft-in soft-out (SISO) decoding of the smaller constituent codes. The complexity of decoding a composite code is directly related to the complexity of SISO decoding the constituent codes. Single-parity-check (SPC) codes are amenable to low-complexity SISO processing because of their simple structure, and as a result, SPC codes are commonly used as constituent codes in composite code designs. The other type of code commonly used in composite code designs is convolutional codes. The regular trellis structure of convolutional codes results in SISO processing implementations of moderate complexity, provided that the number of states is small (e.g., 8 states). Various adjectives are used in this document to described data elements that are shared between constituent codes of a composite code, including “shared”, “overlapped”, and “interlocked”.
Parallel concatenation of convolutional codes (PCCC) is a powerful type of code structure introduced in 1993 in: C. Berrou, A. Glavieux, and P. Thitimajshima, “Near Shannon Limit Error-Correcting Coding and Decoding: Turbo-Codes”, in Proceedings, ICC '93, Geneva, Switzerland, May 1993, pp. 1064-1070. This paper is incorporated herein by reference. PCCC codes are commonly referred to as “Turbo codes”. A PCCC code consists of two or more (usually recursive) systematic convolutional codes that overlap in their systematic portion, with the overlapping data elements having different orderings for each convolutional code. PCCC codes are particularly well-suited to lower code rate applications (e.g., r=⅓) and modest error-rate requirements (e.g., bit-error-rate BER above 10^−6), and can offer excellent performance for these types of applications.
There is no code structure to the interleaved data elements of a Turbo code. A Turbo code is a parallel arrangement of two or more systematic convolutional codes, where the constituent codes overlap in their systematic (i.e., source) portion only (hence, “parallel”). That is, with Turbo codes, only the information bits (or, in general, “information data elements”) are interleaved. Thus, there is no code structure to the interleaved bits of a Turbo code, considered in isolation—they are simply information bits, and could be anything. (Note that there may be a tiny amount of code structure to the interleaved data elements of a Turbo code due to “trellis termination”, but this level of structure does not provide any useful level of error-correction capability, and so can be ignored.)
A fundamental attribute of a PCCC code structure is that, for each of the convolutional codes that overlap, error event span can be increased indefinitely without an associated increase in interlocked (interleaved) weight. As error event span increases, total weight increases, but interlocked weight does not necessarily increase. In essence, with PCCC composite codes, interlocked weight is not coupled to event span for any of the constituent codes. This fundamental attribute of PCCC codes adversely affects their error-correcting performance at low error rates, with the problem being more pronounced the higher the code rate and/or the fewer the number of states.
Another type of composite code structure using convolutional codes was proposed in: S. Benedetto, G. Montorsi, D. Divsalar, and F. Pollara, “Serial concatenation of interleaved codes: Performance analysis, design, and iterative decoding”, JPL TDA Progress Report, vol 42-126, August 1996. This report is incorporated herein by reference. The authors proposed serial concatenation of convolutional codes (SCCC). SCCC codes, like PCCC codes, consist of overlapping convolutional codes, but with SCCC, all of the (unpunctured) coded data elements of one convolutional code are provided as information data elements to a second convolutional code, with the second code being systematic and recursive. A disadvantage of SCCC, however, is that decoder hardware complexity is roughly doubled, on a per-state basis, as compared to PCCC. This is a direct consequence of the fact that with the first constituent code of an SCCC code, there are many state transition intervals where more than one data element is interleaved (or, more precisely, more data elements are interleaved than are necessary to determine the state transition). This means that in the iterative decoding of an SCCC code, soft-in soft-out processing needs to be able to provide soft outputs for not one but two data elements per state transition interval. As a result, non-local connectivity requirements, a dominant factor in implementation complexity, double. The fact that some state transition intervals have more than one interlocked (interleaved) data element is an inherent property of SCCC codes.
Turbo codes and SCCC codes both use convolutional codes as constituent codes to form a composite code structure. The regular trellis structure of convolutional codes makes moderate-complexity SISO decoder implementations possible, and this is why composite code designs for iterative decoding have focussed on covolutional codes as constituent codes (SPC codes are also used as constituent codes in LDPC codes (low density parity check codes). With convolutional constituent codes, however, there is an inevitable trade-off: either low-error rate performance is degraded, if only one data element per state transition interval is interlocked (interleaved), or decoder complexity is increased, if more than one data element per state transition interval is interlocked. That is, if only one data element per state transition is “overlapped”, performance at low error-rates suffers. On the other hand, if two data elements per state transition are “overlapped”, hardware decoder complexity is increased. This trade-off is inherent to the use of convolutional codes as constituent codes in composite code structures.
It would be highly advantageous to have a code for use as a constituent code in composite codes with which, with as few as a single interlocked data element per state transition interval, interlocked weight would rise with increasing event span, thus allowing better performance at low error rates without incurring a penalty in terms of hardware decoder complexity.